package LeetCode.Leet700_799.Leet730_739.Leet739;

import java.util.LinkedList;

/**
 * @ClassName Solution
 * @Author 孙天赐
 * @Date 2025/9/13 14:46
 * @Description TODO: 单调栈 24ms   92.76%
 */
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        // 单调栈，存放元素下标（天数），站内元素代表的天数的气温从栈底到栈顶是递减的
        LinkedList<Integer> stack = new LinkedList<>();
        for(int i = 0;i < temperatures.length;i++){
            // 查看当前i位置的气温，逐个弹出栈中温度低于该温度的元素，并设置对应下标的值
            while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                int t = stack.pop(); // t：某个元素下标，表示该已经找到了后面气温更高的一天
                result[t] = i - t;
            }
            // 当前元素入栈
            stack.push(i);
        }
        // 最后剩下的元素，都是右侧没有更高气温的日期
        while(!stack.isEmpty()){
            result[stack.pop()] = 0;
        }
        return result;
    }
}